package stack;

import org.junit.Test;

import java.util.Stack;

/**
 * @author kunkun
 * @className LeetCode_84
 * @Description ...
 * @date 2025/3/18 13:28
 */
public class LeetCode_84 {

    @Test
    public void test(){
        System.out.println(largestRectangleArea(new int[]{5,4,1,2}));  //8
    }

    public int largestRectangleArea(int[] heights) {

        return solution_1(heights);
    }

    private int solution_1(int[] heights) {
        //1. if条件判断
        if (heights.length == 0){
            return 0;
        }
        //2. 定义单调栈，返回结果，第一个元素入栈（下标）
        Stack<Integer> stack = new Stack<>();
        int result = -1;
        stack.push(0);
        //3. 循环，直至所有元素加入栈中
        for (int i = 1; i <= heights.length-1; i++) {
            if (!stack.isEmpty() && heights[i]<heights[stack.peek()]){
                while (!stack.isEmpty() && heights[i]<heights[stack.peek()]){
                    Integer num = stack.pop();
                    int tempRes;
                    if (stack.isEmpty()){
                        tempRes = heights[num]*i;
                    }else{
                        tempRes = heights[num]*(i-1-stack.peek());
                    }
                    result = Math.max(result,tempRes);
                }
            }
            stack.push(i);
        }
        //4. 逐一弹出
        while (!stack.isEmpty()){
            Integer num = stack.pop();
            int tempRes;
            if (stack.isEmpty()){
                tempRes = heights[num]*heights.length;
            }else{
                tempRes = heights[num]*(heights.length-1-stack.peek());
            }
            result = Math.max(result,tempRes);
        }
        return result;
    }

}
